package leecode

import (
	"container/list"
	"math"
)

func maxLevelSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	queue := list.New()
	queue.PushBack(root)
	result := math.MinInt
	index := 1
	hashMap := make(map[int]int) //key为每层的和 , value为第几层
	for queue.Len() != 0 {
		sum := 0
		size := queue.Len()
		for i := 0; i < size; i++ {
			node := queue.Remove(queue.Front()).(*TreeNode)
			if node.Left != nil {
				queue.PushBack(node.Left)
			}
			if node.Right != nil {
				queue.PushBack(node.Right)
			}
			sum += node.Val
		}
		if _, ok := hashMap[sum]; !ok {
			hashMap[sum] = index
		}
		result = max(result, sum)
		index++
	}
	return hashMap[result]
}
